package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Lc108 {


    public TreeNode sortedArrayToBST(int[] nums) {

        return getBST(nums, 0, nums.length - 1);
    }

    public TreeNode getBST(int[] nums, int l, int r) {
        if (l > r)
            return null;
        int mid = (l + r) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = getBST(nums, l, mid - 1);
        root.right = getBST(nums, mid + 1, r);
        return root;
    }

    public ListNode sortList(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode node = head;
        while(head.next != null) {
            list.add(head.val);
            node = node.next;
        }
        Collections.sort(list);
        node = head;
        int idx = 0;
        while (node.next != null) {
            node.val = list.get(idx++);
            node = node.next;
        }
        return head;
    }
}
